﻿//#define TRACE_EVERY
#define TRACE_LAST

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions
{
    /*
     * By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and making use of the four arithmetic operations (+, −, *, /) and brackets/parentheses, it is possible to form different positive integer targets.

For example,

8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) − 1
36 = 3 * 4 * (2 + 1)

Note that concatenations of the digits, like 12 + 34, are not allowed.

Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one different target numbers of which 36 is the maximum, and each of the numbers 1 to 28 can be obtained before encountering the first non-expressible number.

Find the set of four distinct digits, a < b < c < d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd.

     * */
    class Problem93 : IProblem
    {
        public string Calculate()
        {
            var q = CommonFunctions.GetCombination(new List<char>() { '1', '2', '3', '4', '5', '6', '7', '8', '9' }, 4);

            int maxCount = 0;
            string maxCombination = " ";

            foreach (string combination in q)
            {
                var q2 = CommonFunctions.GetPermutation(combination.ToList());

                HashSet<long> solutions = new HashSet<long>();

                foreach (var number in q2)
                {

                    foreach (var o in GetOperators())
                    {
                        long nominator, denominator, nominator2, denominator2, solutionNominator, solutionDenominator;

                        //(a b) (c d)
                        PerformOperation(number[0] - '0', number[1] - '0', o[0], out nominator, out denominator);
                        PerformOperation(number[2] - '0', number[3] - '0', o[2], out nominator2, out denominator2);
                        PerformOperation(nominator, denominator, nominator2, denominator2, o[1], out solutionNominator, out solutionDenominator);

#if TRACE_EVERY
                    Console.WriteLine("({0}{1}{2}){3}({4}{5}{6}) = {7}", number[0], o[0], number[1], o[1], number[2], o[2], number[3], solutionNominator / (double)solutionDenominator);
#endif
                        if (solutionDenominator != 0 && solutionNominator % solutionDenominator == 0 && solutionNominator / solutionDenominator > 0)
                            solutions.Add(solutionNominator / solutionDenominator);

                        //((a b) c) d
                        PerformOperation(number[0] - '0', number[1] - '0', o[0], out nominator, out denominator);
                        PerformOperation(nominator, denominator, number[2] - '0', 1, o[1], out nominator2, out denominator2);
                        PerformOperation(nominator2, denominator2, number[3] - '0', 1, o[2], out solutionNominator, out solutionDenominator);
#if TRACE_EVERY
                    Console.WriteLine("(({0}{1}{2}){3}{4}){5}{6} = {7}", number[0], o[0], number[1], o[1], number[2], o[2], number[3], solutionNominator / (double)solutionDenominator);
#endif
                        if (solutionDenominator != 0 && solutionNominator % solutionDenominator == 0 && solutionNominator / solutionDenominator > 0)
                            solutions.Add(solutionNominator / solutionDenominator);

                        //(a (b c)) d
                        PerformOperation(number[1] - '0', number[2] - '0', o[1], out nominator, out denominator);
                        PerformOperation(number[0] - '0', 1, nominator, denominator, o[0], out nominator2, out denominator2);
                        PerformOperation(nominator2, denominator2, number[3] - '0', 1, o[2], out solutionNominator, out solutionDenominator);
#if TRACE_EVERY
                    Console.WriteLine("({0}{1}({2}{3}{4}){5}{6}) = {7}", number[0], o[0], number[1], o[1], number[2], o[2], number[3], solutionNominator / (double)solutionDenominator);
#endif
                        if (solutionDenominator != 0 && solutionNominator % solutionDenominator == 0 && solutionNominator / solutionDenominator > 0)
                            solutions.Add(solutionNominator / solutionDenominator);

                        //a ((b c) d)
                        PerformOperation(number[1] - '0', number[2] - '0', o[1], out nominator, out denominator);
                        PerformOperation(nominator, denominator, number[3] - '0', 1, o[2], out nominator2, out denominator2);
                        PerformOperation(number[0] - '0', 1, nominator2, denominator2, o[0], out solutionNominator, out solutionDenominator);
#if TRACE_EVERY
                    Console.WriteLine("{0}{1}(({2}{3}{4}){5}{6}) = {7}", number[0], o[0], number[1], o[1], number[2], o[2], number[3], solutionNominator / (double)solutionDenominator);
#endif
                        if (solutionDenominator != 0 && solutionNominator % solutionDenominator == 0 && solutionNominator / solutionDenominator > 0)
                            solutions.Add(solutionNominator / solutionDenominator);

                        //a (b (c d))
                        PerformOperation(number[2] - '0', number[3] - '0', o[2], out nominator, out denominator);
                        PerformOperation(number[1] - '0', 1, nominator, denominator, o[1], out nominator2, out denominator2);
                        PerformOperation(number[0] - '0', 1, nominator2, denominator2, o[0], out solutionNominator, out solutionDenominator);
#if TRACE_EVERY
                    Console.WriteLine("(({0}{1}{2}){3}{4}){5}{6} = {7}", number[0], o[0], number[1], o[1], number[2], o[2], number[3], solutionNominator / (double)solutionDenominator);
#endif
                        if (solutionDenominator != 0 && solutionNominator % solutionDenominator == 0 && solutionNominator / solutionDenominator > 0)
                            solutions.Add(solutionNominator / solutionDenominator);
                    }
                }

                var q3 = solutions.OrderBy(x => x);
                int i = 1;
                int count = 0;
                foreach (var s in q3)
                {
                    if (s != i)
                        break;
                    i++;
                    count++;
                }

                if (count > maxCount)
                {
                    maxCount = count;
                    maxCombination = combination;
                    Console.WriteLine(count);
                }
            }

            return maxCombination;
        }

        void PerformOperation(long aNom, long aDenom, long bNom, long bDenom, char op, out long nom, out long denom)
        {
            switch (op)
            {
                case '*':
                    nom = aNom * bNom;
                    denom = aDenom * bDenom;
                    break;
                case '/':
                    nom = aNom * bDenom;
                    denom = aDenom * bNom;
                    break;
                case '+':
                    nom = aNom * bDenom + bNom * aDenom;
                    denom = aDenom * bDenom;
                    break;
                case '-':
                    nom = aNom * bDenom - bNom * aDenom;
                    denom = aDenom * bDenom;
                    break;
                default:
                    nom = 0;
                    denom = 1;
                    break;
            }

            if (nom == 0)
            {
                denom = 1;
            }
            else if (denom == 0)
            {
                nom = 0;
            }
            else
            {
                long gcd = CommonFunctions.GreatestCommonDivisor(Math.Abs(nom), Math.Abs(denom));
                nom /= gcd;
                denom /= gcd;
                if (denom < 0)
                {
                    denom = -denom;
                    nom = -nom;
                }
            }
        }

        void PerformOperation(int a, int b, char op, out long nominator, out long denominator)
        {
            switch (op)
            {
                case '*':
                    nominator = a * b;
                    denominator = 1;
                    break;
                case '/':
                    long gcd = CommonFunctions.GreatestCommonDivisor(a, b);
                    nominator = a / gcd;
                    denominator = b / gcd;
                    break;
                case '+':
                    nominator = a + b;
                    denominator = 1;
                    break;
                case '-':
                    nominator = a - b;
                    denominator = 1;
                    break;
                default:
                    nominator = 0;
                    denominator = 1;
                    break;
            }
        }

        public IEnumerable<string> GetOperators()
        {
            String operators = "*/+-";

            for (int i = 0; i < 4; i++)
            {
                for (int j = 0; j < 4; j++)
                {
                    for (int k = 0; k < 4; k++)
                    {
                        yield return operators[i].ToString() + operators[j].ToString() + operators[k].ToString();
                    }
                }
            }
        }
    }
}
